package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *@author 周杨
 *Sum3_15_ 给定一个无序数组 寻找三个元素加起来和等于0 用list保存这三个元素 要求不能有重复的集合
 *describe:先排序 然后双指针遍历  AC 51%
 *2018年12月21日 下午8:39:01
 */
public class Sum3_15_ {
	public static void main(String[] args) {
		Sum3_15_ test=new Sum3_15_();
		test.threeSum(new int[] {-1,0,1,2,-1,-4});//-4 -1 -1 0 1 2
	}
	
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		for(int i=0;i<nums.length;++i) {
			if(i!=0&&nums[i]==nums[i-1]) continue;
			int left=i+1,right=nums.length-1;
			int target=-nums[i];
			while(left<right) {
				int sum=nums[left]+nums[right];
				if(sum==target) {
					res.add(Arrays.asList(nums[i],nums[left],nums[right]));
					++left;
					--right;
					while(left<right&&nums[left]==nums[left-1]) ++left;
					while(right>left&&nums[right]==nums[right+1]) --right;
				}
				else if(sum>target)
					--right;
				else 
					++left;
			}
		}
		return res;
	}
}
